package com.company.algo.niuke;

import java.util.ArrayList;
import java.util.Arrays;

/**腾讯：最小的K个数
 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
 直接用快排【做过但想不起来】
 */
public class GetLeastNumbers {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (k>input.length) return arr2List(input);
        return quickSort(input,k,0,input.length-1);
    }

    private ArrayList<Integer> quickSort(int[] input, int k, int left, int right) {
        int i = left, j = right;
        while (i<j){
            while (i<j && input[j]>=input[left]) j--;
            while (i<j && input[i] <= input[left]) i++;
            swap(input,i,j);
        }
        swap(input,i,left);
        if (i > k) return quickSort(input,k,left,i-1);
        if (i < k) return quickSort(input,k,i+1, right);
        return arr2List(Arrays.copyOf(input,k));
    }

    private void swap(int[] input, int i, int j) {
        int tmp = input[i];
        input[i] = input[j];
        input[j] = tmp;
    }

    private ArrayList<Integer> arr2List(int[] input) {
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.stream(input).forEach(list::add);
        return list;
    }

    public static void main(String[] args) {
        GetLeastNumbers Main = new GetLeastNumbers();
        int[] input = {4,5,1,6,2,7,3,8};
        System.out.println(Main.GetLeastNumbers_Solution(input, 4));
    }
}
